home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / HASH_TAB.C < prev    next >
C/C++ Source or Header  |  1992-09-28  |  20KB  |  483 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/Hash_Table.h>
  14.  
  15. // compare_keys_s -- Key compare
  16. template <class Tkey, class Tval> 
  17. Boolean (*CoolHash_Table<Tkey,Tval>::compare_keys_s)
  18.    (const Tkey&, const Tkey&) = &CoolHash_Table_keys_equal;
  19. //##CoolHash_Table<Tkey,Tval>::Key_Compare CoolHash_Table<Tkey,Tval>::compare_keys_s = &CoolHash_Table_keys_equal;
  20.  
  21. // compare_values_s -- Value compare
  22. template <class Tkey, class Tval> 
  23. Boolean (*CoolHash_Table<Tkey,Tval>::compare_values_s) (const Tval&, const Tval&) = &CoolHash_Table_values_equal;
  24. //##CoolHash_Table<Tkey,Tval>::Value_Compare CoolHash_Table<Tkey,Tval>::compare_values_s = &CoolHash_Table_values_equal;
  25.  
  26. // CoolHash_Table -- Simple constructor with no arguments that creates a hash
  27. //               table object with the minimal prime number of buckets and
  28. //               uses the default hash function.
  29. // Input:        None
  30. // Output:       None
  31.  
  32. template <class Tkey, class Tval> 
  33. CoolHash_Table<Tkey,Tval>::CoolHash_Table() {
  34.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  35.   this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  36.   this->h_function = &CoolHash_Table_default_hash;
  37. }
  38.  
  39.  
  40. // CoolHash_Table -- Simple constructor with one argument that creates a hash
  41. //               table object with the minimal prime number of buckets that
  42. //               holds some user-supplied number of items and uses the default
  43. //               hash function.
  44. // Input:        Minimal number of items table must hold
  45. // Output:       None
  46.  
  47. template <class Tkey, class Tval> 
  48. CoolHash_Table<Tkey,Tval>::CoolHash_Table(unsigned long n)
  49. : CoolBase_Hash_Table(n)
  50. {
  51.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  52.   this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  53.   this->h_function = &CoolHash_Table_default_hash;
  54. }
  55.  
  56.  
  57. // CoolHash_Table -- constructor that takes a reference to an existing hash table
  58. //               and duplicates both its size and contents
  59. // Input:        Reference to hash table object
  60. // Output:       None
  61.  
  62. template <class Tkey, class Tval> 
  63. CoolHash_Table<Tkey,Tval>::CoolHash_Table(const CoolHash_Table<Tkey,Tval>& h)
  64. : CoolBase_Hash_Table(h)
  65. {
  66.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  67.   this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  68.   for (long i = 0; i < prime; i++) { // For each bucket count
  69.     for (int j = 0; j < h.items_in_buckets[i]; j++) { // For items in bucket
  70.       this->table[i].data[j].key = h.table[i].data[j].key; // Copy key 
  71.       this->table[i].data[j].value = h.table[i].data[j].value; // Copy value
  72.     }
  73.   }
  74.   this->h_function = h.h_function;        // Use the same hash function
  75. }
  76.  
  77.  
  78. // ~CoolHash_Table -- Destructor for the CoolHash_Table class
  79. // Input:         this*
  80. // Output:        None
  81.  
  82. template <class Tkey, class Tval> 
  83. CoolHash_Table<Tkey,Tval>::~CoolHash_Table() {
  84.   delete [] this->table;            // Free key/value storage
  85. }
  86.  
  87.  
  88. // find -- Find key/value in hash table
  89. // Input:  Key searching for
  90. // Output: TRUE/FALSE; current_position updated
  91.  
  92. template <class Tkey, class Tval> 
  93. Boolean CoolHash_Table<Tkey,Tval>::find (const Tkey& key) {
  94.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  95.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value 
  96.   for (int i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
  97.     if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE){
  98.       this->curpos = SET_BUCKET_NUMBER(hash); // Set bucket number
  99.       this->curpos |= SET_BUCKET_INDEX(i);      // Set bucket index
  100.       return TRUE;                // Return success
  101.     }
  102.   }
  103.   return FALSE;
  104. }
  105.  
  106.  
  107. // key --  Return key at current position
  108. // Input:  None
  109. // Output: Reference to key at current position
  110.  
  111. template <class Tkey, class Tval> 
  112. const Tkey& CoolHash_Table<Tkey,Tval>::key () {
  113.   if (this->curpos != INVALID) { // If valid current position
  114.     unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
  115.     long index = BUCKET_INDEX(this->curpos);          // Get index in bucket
  116.     return (this->table[hash].data[index].key);          // Return value
  117.   }
  118.   else                // Else 
  119.     this->key_error ("Tkey","Tval"); // Raise exception
  120. }
  121.  
  122.  
  123. // value -- Return value at current position
  124. // Input:   None
  125. // Output:  Reference to value at current position
  126.  
  127. template <class Tkey, class Tval> 
  128. const Tval& CoolHash_Table<Tkey,Tval>::value () {
  129.   if (this->curpos != INVALID) { // If valid current position
  130.     unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
  131.     long index = BUCKET_INDEX(this->curpos);          // Get index in bucket
  132.     return (this->table[hash].data[index].value);     // Return value
  133.   }
  134.   else                // Else 
  135.     this->value_error ("Tkey","Tval"); // Raise exception
  136. }
  137.  
  138.  
  139. // put -- Hash key/value pair into table if not already there
  140. // Input: this*, key, value
  141. // Output:TRUE when key is new, else FALSE
  142.  
  143. template <class T1, class T2> 
  144. Boolean CoolHash_Table<T1,T2>::put (const T1& key, const T2& value) {
  145.  retry:
  146.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  147.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  148.   int index = this->items_in_buckets[hash];
  149.   this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
  150.   for (int i = 0; i < index; i++)      // For each item
  151.     if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
  152.       this->table[hash].data[i].value = value; // Already there, update value
  153.       this->curpos |= SET_BUCKET_INDEX(i);       // Update bucket index position
  154.       return FALSE;                 // And return found
  155.     }
  156.   if (index >= BUCKET_SIZE) {    // If bucket is full
  157.     this->resize (hash_primes[this->current_bucket+1]*BUCKET_SIZE); // Grow
  158.     goto retry;
  159.   }
  160.   this->table[hash].data[index].key = key;
  161.   this->table[hash].data[index].value = value;
  162.   this->entry_count++;    // Increment table entry count
  163.   this->curpos |= SET_BUCKET_INDEX(index); // Update bucket index position
  164.   this->items_in_buckets[hash]++;       // Increment bucket item count
  165.   return TRUE;               // Indicate new
  166. }
  167.  
  168.  
  169. // get -- Get a value based on a key from the table
  170. // Input: this*, reference to a key
  171. // Output:Value for key/value pair from table
  172. //        Returns TRUE when entry is found, else false
  173.  
  174. template <class Tkey, class Tval> 
  175. Boolean CoolHash_Table<Tkey,Tval>::get (const Tkey& key, Tval& value) {
  176.   Boolean result = FALSE;    // Assume we don't find entry
  177.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  178.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  179.   for (int i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
  180.     if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
  181.       this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
  182.       this->curpos|= SET_BUCKET_INDEX(i);          // Save index into bucket
  183.       value = this->table[hash].data[i].value;          // Copy value in table
  184.       result = TRUE;                      // Inidicate success
  185.       break;                          // Break out of loop
  186.     }
  187.   }
  188.   return result;        // Return success/failure
  189. }
  190.  
  191.  
  192. // get_key --Get a key based on a value from the table
  193. // Input:    this*, reference to a value, reference to place to store key
  194. // Output:   TRUE if found with value in reference argument, else FALSE
  195.  
  196. template <class Tkey, class Tval> 
  197. Boolean CoolHash_Table<Tkey,Tval>::get_key (const Tval& value, Tkey& key) {
  198.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  199.   for (long i = 0; i < prime; i++)          // For each bucket, search
  200.     for (int j = 0; j < this->items_in_buckets[i]; j++) // For item in bucket
  201.       if ((*this->compare_values_s)(value,this->table[i].data[j].value)==TRUE){
  202.     this->curpos = SET_BUCKET_NUMBER(i); // Set bucket number
  203.     this->curpos|= SET_BUCKET_INDEX(j);         // Set index into bucket
  204.     key = this->table[i].data[j].key;             // Return key for value
  205.     return TRUE;                         // Indicate success
  206.       }
  207.   return FALSE;        // Indicate failure
  208. }
  209.  
  210.  
  211. // remove -- Remove element at current position from the set
  212. // Input:    this*
  213. // Output:   TRUE/FALSE
  214.  
  215. template <class Tkey, class Tval> 
  216. Boolean CoolHash_Table<Tkey,Tval>::remove () {
  217.   if (this->curpos != INVALID) { // If valid current position
  218.     unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
  219.     long index = BUCKET_INDEX(this->curpos);          // Get index in bucket
  220.     int count = this->items_in_buckets[hash];          // Number of items in bucket
  221.     this->table[hash].data[index].key = this->table[hash].data[count-1].key;
  222.     this->table[hash].data[index].value = this->table[hash].data[count-1].value;
  223.     this->entry_count--;    // Decrement table entry count
  224.     this->items_in_buckets[hash]--; // Decrement bucket item count
  225.     if (this->items_in_buckets[hash]) {    // If any more items in bucket
  226.       this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
  227.       this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
  228.     }
  229.     else
  230.       this->curpos = INVALID;    // Else invalidate marker
  231.     return TRUE;        // Return success
  232.   }
  233.   this->remove_error ("Tkey", "Tval"); // Raise exception
  234.   return FALSE;             // Return failure
  235. }
  236.  
  237.  
  238. // remove -- Remove a value based on a key from the table
  239. // Input:    this*, reference to a key
  240. // Output:   TRUE/FALSE
  241.  
  242. template <class Tkey, class Tval> 
  243. Boolean CoolHash_Table<Tkey,Tval>::remove (const Tkey& key) {
  244.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  245.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  246.   int count = this->items_in_buckets[hash];           // Number of items in bucket
  247.   for (int i = 0; i < count; i++) {               // For each entry in bucket
  248.     if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
  249.       this->table[hash].data[i].key = this->table[hash].data[count-1].key;
  250.       this->table[hash].data[i].value = this->table[hash].data[count-1].value;
  251.       this->entry_count--;    // Decrement table entry count
  252.       this->items_in_buckets[hash]--; // Decrement bucket item count
  253.       if (this->items_in_buckets[hash]) {    // If any more items in bucket
  254.     this->curpos = SET_BUCKET_NUMBER(hash);    // Save bucket number
  255.     this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
  256.       }
  257.       else
  258.     this->curpos = INVALID;    // Else invalidate marker
  259.       return TRUE;
  260.     }
  261.   }
  262.   return FALSE;        // Return failure flag
  263. }
  264.  
  265.  
  266. // resize -- Resize a hash table object to hold at least some number items
  267. // Input:    this*, minimum number of items to hold
  268. // Output:   None
  269.  
  270. template <class Tkey, class Tval> 
  271. void CoolHash_Table<Tkey,Tval>::resize (long n) {
  272. #if ERROR_CHECKING
  273.   if (n < 0)            // If invalid size
  274.     this->resize_error ("Tkey", "Tval", n); // Raise exception
  275. #endif
  276.   CoolHash_Table_Bucket<Tkey,Tval>* t2; // Temporary variable
  277.   long old_prime = hash_primes[this->current_bucket]; // Get prime number 
  278.   while (hash_primes[this->current_bucket]*BUCKET_SIZE < n) // Find prime big
  279.     this->current_bucket++;                    // ... enough for number items
  280.   if (this->growth_ratio != 0.0) {                // If a growth ratio is set
  281.     int new_size = int((old_prime * BUCKET_SIZE) * (1.0 + this->growth_ratio));
  282.     if (new_size > n)
  283.       while (hash_primes[this->current_bucket]*BUCKET_SIZE < new_size)
  284.     this->current_bucket++;    // Enough size for growth ratio
  285.   }
  286.  retry:
  287.   long new_prime = hash_primes[this->current_bucket]; // Get prime number 
  288.   unsigned char* t1 = new unsigned char[new_prime];   // Counts items in buckets
  289.   for (long i = 0; i < new_prime; i++)        // For each bucket count
  290.     t1[i] = 0;                    // Initialize to zero
  291.   // NOTE: We should use the overloaded operator new to construct only
  292.   //       the new buckets, and use memcpy instead of operator= for copying
  293.   t2 = new CoolHash_Table_Bucket<Tkey,Tval>[new_prime]; 
  294.   for (i = 0; i < old_prime; i++) { // For each bucket count
  295.     CoolHash_Table_Pair<Tkey,Tval>* data = this->table[i].data;
  296.     for (int j = 0; j < this->items_in_buckets[i]; j++) { // For each item
  297.       unsigned long hash = ((*this->h_function)(data[j].key)) % new_prime;
  298.       if (t1[hash] == BUCKET_SIZE) { // Overflow bucket -- resize
  299.     delete [] t1;                 // Delete allocated storage
  300.     delete [] t2;                 // Delete allocated storage
  301.     this->current_bucket++;             // Increment bucket count
  302.     goto retry;                 // Go retry again
  303.       }
  304.       t2[hash].data[t1[hash]].key = data[j].key; // Copy key into new table
  305.       t2[hash].data[t1[hash]].value = data[j].value; //Copy value into new table
  306.       t1[hash]++;                         // Increment bucket item count
  307.     }
  308.   }
  309.   delete [] this->items_in_buckets;        // Free up old storage
  310.   delete [] this->table;            // Free up old storage
  311.   this->items_in_buckets = t1;            // Point to new item count
  312.   this->table = t2;                // Point to new buckets
  313.   this->curpos = INVALID;            // Invalidate current position
  314. }
  315.  
  316. // Operator= -- Assignment of one hash table to another duplicating size and
  317. //              contents and returning old storage
  318. // Input:       Reference to hash table object
  319. // Output:      Reference to new hash table object
  320.  
  321. template <class Tkey, class Tval> 
  322. CoolHash_Table<Tkey,Tval>& CoolHash_Table<Tkey,Tval>::operator= (const CoolHash_Table<Tkey,Tval>& h) {
  323.   if (this != &h) {
  324.     CoolBase_Hash_Table::operator=(h);
  325.     long prime = hash_primes[this->current_bucket]; // Get prime number
  326.     delete [] this->table;                // Return old table storage
  327.     this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  328.     for (long i = 0; i < prime; i++) {        // For each bucket count
  329.       for (int j = 0; j < h.items_in_buckets[i]; j++) { // For each item in bucket
  330.     this->table[i].data[j].key = h.table[i].data[j].key; // Copy key 
  331.     this->table[i].data[j].value = h.table[i].data[j].value; // Copy value
  332.       }
  333.     }
  334.     this->compare_keys_s = h.compare_keys_s;    // Use same compare function
  335.     this->compare_values_s = h.compare_values_s; // Use same compare function
  336.   }
  337.   return *this;                // Return reference
  338. }
  339.  
  340. // operator== -- Determine if two hash tables are equal. This is accomplished
  341. //               by seeing that for each key/value pair in table1, there is the
  342. //               the same pair somewhere in table2.
  343. // Input:        Reference to hash table
  344. // Output:       TRUE/FALSE
  345.  
  346. template <class Tkey, class Tval> 
  347. Boolean CoolHash_Table<Tkey,Tval>::operator==(const CoolHash_Table<Tkey,Tval>& h) {
  348.   if (this->length() != h.length()) // If not same number of entries
  349.     return FALSE;            // Then tables are not equal
  350.   if (this->get_bucket_count() == h.get_bucket_count()) { // If same bucket cnt
  351.     for (long i = 0; i < this->get_bucket_count(); i++) { // for each bucket
  352.       int count = this->get_count_in_bucket(i);
  353.       if (count != h.get_count_in_bucket(i)) //Count eq?
  354.     return FALSE;                 // No, tables !equal
  355.       CoolHash_Table_Pair<Tkey,Tval>* this_bucket = this->table[i].data;
  356.       CoolHash_Table_Pair<Tkey,Tval>* h_bucket = h.table[i].data;
  357.       for (int j = 0; j < count; j++) { // For each item in this
  358.     for (int k = 0; k < count; k++) {    // For each item in h
  359.       if ((*this->compare_keys_s)(this_bucket[j].key, h_bucket[k].key)) {
  360.         if ((*this->compare_values_s)(this_bucket[j].value, // key same,
  361.                       h_bucket[j].value))                        // is value?
  362.           goto good;
  363.         return FALSE;        // Not the same, so tables !eql
  364.       }
  365.     }
  366.       good: ;
  367.       }
  368.     }
  369.     return TRUE;        // No difference, so equal
  370.   } else {
  371.     Tval temp;            // Temporary storage;
  372.     for (long i = 0; i < h.get_bucket_count (); i++) { // For each bucket
  373.       for (int j = 0; j < h.get_count_in_bucket(i); j++) // For each item
  374.     if (this->get (h.table[i].data[j].key, temp) == TRUE) // If key in table
  375.       if ((*this->compare_values_s)(h.table[i].data[j].value, temp))
  376.         continue;        // Key/value same, continue
  377.       else
  378.         return FALSE;    // Value different, return FALSE
  379.     else
  380.       return FALSE;        // Key not in table so different
  381.     }
  382.   }
  383.   return TRUE;        // No difference, so equal
  384. }
  385.  
  386.  
  387. // set_key_compare -- Set the compare function for this instance
  388. // Input:             Pointer to compare function
  389. // Output:            None
  390.  
  391. template <class Tkey, class Tval> 
  392. void CoolHash_Table<Tkey,Tval>::set_key_compare (Boolean (*c) (const Tkey&, const Tkey&)) {
  393.   if (c == NULL)        // If no method supplied
  394.     this->compare_keys_s = &CoolHash_Table_keys_equal;
  395.   else
  396.     this->compare_keys_s = c;
  397. }
  398.  
  399.  
  400. // set_value_compare -- Set the compare function for this instance
  401. // Input:               Pointer to compare function
  402. // Output:              None
  403.  
  404. template <class Tkey, class Tval> 
  405. void CoolHash_Table<Tkey,Tval>::set_value_compare(Boolean (*c) (const Tval&, const Tval&)) {
  406.   if (c == NULL)
  407.     this->compare_values_s = &CoolHash_Table_values_equal;
  408.   else
  409.     this->compare_values_s = c;
  410. }
  411.  
  412. // operator<< -- Overload the output operator to provide a crude print
  413. //               capability for hash table objects
  414. // Input:        ostream reference, hash table reference
  415. // Output:       None
  416.  
  417. template <class Tkey, class Tval>
  418. ostream& operator<< (ostream& os, const CoolHash_Table<Tkey,Tval>& h) {
  419.   for (long i = 0; i < h.get_bucket_count(); i++) { // For each bucket
  420.     for (int j = 0; j < h.get_count_in_bucket(i); j++) { // For each key/pair
  421.       os << "(" << h.table[i].data[j].key;         // Output the key
  422.       os << "," << h.table[i].data[j].value;         // Output the value
  423.       os << ")\n";                     // And a newline
  424.     }
  425.   }
  426.   return os;            // Return refererence to stream
  427. }
  428.  
  429. // included to define their default equality and hash functions
  430. #include <string.h>  // strcmp(const char*, const char*)
  431. #include <cool/String.h>
  432. #include <cool/Gen_String.h>
  433.  
  434. // specific
  435. Boolean CoolHash_Table_keys_equal (char* const& v1, char* const& v2)
  436.   { return !strcmp (v1, v2); }
  437. unsigned long CoolHash_Table_default_hash (char* const& key)
  438.   { return sxhash(key); }
  439.  
  440. unsigned long CoolHash_Table_default_hash (const CoolString& key)
  441.   { return sxhash(key); }
  442.  
  443. unsigned long CoolHash_Table_default_hash (const CoolGen_String& key)
  444.   { return sxhash(key); }
  445.  
  446.  
  447. // are_keys_equal -- Compares two keys using the user supplied comparison
  448. //                   function or the built-in operator== otherwise
  449. // Input:            References to two keys
  450. // Output:           TRUE/FALSE
  451.  
  452. template <class Tkey>
  453. Boolean CoolHash_Table_keys_equal (const Tkey& k1, const Tkey& k2) {
  454.   return (k1 == k2);
  455. }
  456.  
  457. // default_hash -- Implements the hash mechanism 
  458. // Input:          Reference to a key
  459. // Output:         Hash value (0-relative index into based table)
  460.  
  461. template <class Tkey>
  462. unsigned long CoolHash_Table_default_hash (const Tkey& key) {
  463.   if (sizeof (Tkey) <= 4)
  464.     return (((unsigned long) key) >> 2);
  465.   else {
  466.     int nlongs = sizeof(Tkey)/sizeof(long);
  467.     register const unsigned long* objp = (const unsigned long*) &key;
  468.     register unsigned long hash = *objp++;
  469.     while (--nlongs > 0) hash ^= *objp++;
  470.     return hash &= 0x7fffffffL;            // Make sure bit 32 is zero
  471.   }
  472. }
  473.  
  474. // are_values_equal -- Compares values using the default operator == function
  475. // Input:              References to two values
  476. // Output:             TRUE/FALSE
  477.  
  478. template <class Tval>
  479. Boolean CoolHash_Table_values_equal (const Tval& v1, const Tval& v2) {
  480.   return (v1 == v2);
  481. }
  482.  
  483.